package com.cqs.leetcode.array;

import java.util.Stack;

/**
 * lixw
 * 2021/11/4
 **/
public class DailyTemperatures739 {


    class Solution {
        //暴力解法O(N^2)
        public int[] dailyTemperatures(int[] temperatures) {
            int[] result = new int[temperatures.length];
            for (int i = 0; i < temperatures.length; i++) {
                for (int j = i + 1; j < temperatures.length; j++) {
                    if (temperatures[j] > temperatures[i]) {
                        result[i] = j - i;
                        break;
                    }
                }
            }
            return result;
        }
    }

    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int[] result = new int[temperatures.length];
        for(int i = 1; i < temperatures.length; i++) {
            while(stack.size() > 0 && temperatures[stack.peek()] < temperatures[i] ) {
                int idx = stack.pop();
                result[idx] = i - idx;
            }
            stack.push(i);
        }
        return result;
    }

}
